/**
 * @license MIT
 * @copyright 2020 Eyas Ranjous <eyas.ranjous@gmail.com>
 */
class Heap {
    /**
     * @param {function} compare 比较函数
     * @param {array} [_values]
     * @param {number|string|object} [_leaf]
     */
    constructor(compare, _values, _leaf) {
        if (typeof compare !== 'function') {
            throw new Error('Heap constructor expects a compare function');
        }
        this._compare = compare;
        this._nodes = Array.isArray(_values) ? _values : [];
        this._leaf = _leaf || null;
    }

    /**
     * Checks if a parent has a left child
     * @private
     */
    _hasLeftChild(parentIndex) {
        const leftChildIndex = (parentIndex * 2) + 1;
        return leftChildIndex < this.size();
    }

    /**
     * Checks if a parent has a right child
     * @private
     */
    _hasRightChild(parentIndex) {
        const rightChildIndex = (parentIndex * 2) + 2;
        return rightChildIndex < this.size();
    }

    /**
     * Compares two nodes
     * @private
     */
    _compareAt(i, j) {
        return this._compare(this._nodes[i], this._nodes[j]);
    }

    /**
     * Swaps two nodes in the heap
     * @private
     */
    _swap(i, j) {
        const temp = this._nodes[i];
        this._nodes[i] = this._nodes[j];
        this._nodes[j] = temp;
    }

    /**
     * Checks if parent and child should be swapped
     * @private
     */
    _shouldSwap(parentIndex, childIndex) {
        if (parentIndex < 0 || parentIndex >= this.size()) {
            return false;
        }

        if (childIndex < 0 || childIndex >= this.size()) {
            return false;
        }

        return this._compareAt(parentIndex, childIndex) > 0;
    }

    /**
     * Compares children of a parent
     * @private
     */
    _compareChildrenOf(parentIndex) {
        if (!this._hasLeftChild(parentIndex) && !this._hasRightChild(parentIndex)) {
            return -1;
        }

        const leftChildIndex = (parentIndex * 2) + 1;
        const rightChildIndex = (parentIndex * 2) + 2;

        if (!this._hasLeftChild(parentIndex)) {
            return rightChildIndex;
        }

        if (!this._hasRightChild(parentIndex)) {
            return leftChildIndex;
        }

        const compare = this._compareAt(leftChildIndex, rightChildIndex);
        return compare > 0 ? rightChildIndex : leftChildIndex;
    }

    /**
     * Compares two children before a position
     * @private
     */
    _compareChildrenBefore(index, leftChildIndex, rightChildIndex) {
        const compare = this._compareAt(rightChildIndex, leftChildIndex);

        if (compare <= 0 && rightChildIndex < index) {
            return rightChildIndex;
        }

        return leftChildIndex;
    }

    /**
     * Recursively bubbles up a node if it's in a wrong position
     * @private
     */
    _heapifyUp(startIndex) {
        let childIndex = startIndex;
        let parentIndex = Math.floor((childIndex - 1) / 2);

        while (this._shouldSwap(parentIndex, childIndex)) {
            this._swap(parentIndex, childIndex);
            childIndex = parentIndex;
            parentIndex = Math.floor((childIndex - 1) / 2);
        }
    }

    /**
     * Recursively bubbles down a node if it's in a wrong position
     * @private
     */
    _heapifyDown(startIndex) {
        let parentIndex = startIndex;
        let childIndex = this._compareChildrenOf(parentIndex);

        while (this._shouldSwap(parentIndex, childIndex)) {
            this._swap(parentIndex, childIndex);
            parentIndex = childIndex;
            childIndex = this._compareChildrenOf(parentIndex);
        }
    }

    /**
     * Recursively bubbles down a node before a given index
     * @private
     */
    _heapifyDownUntil(index) {
        let parentIndex = 0;
        let leftChildIndex = 1;
        let rightChildIndex = 2;
        let childIndex;

        while (leftChildIndex < index) {
            childIndex = this._compareChildrenBefore(
                index,
                leftChildIndex,
                rightChildIndex
            );

            if (this._shouldSwap(parentIndex, childIndex)) {
                this._swap(parentIndex, childIndex);
            }

            parentIndex = childIndex;
            leftChildIndex = (parentIndex * 2) + 1;
            rightChildIndex = (parentIndex * 2) + 2;
        }
    }

    /**
     * Inserts a new value into the heap
     * @public
     * @param {number|string|object} value
     * @returns {Heap}
     */
    insert(value) {
        this._nodes.push(value);
        this._heapifyUp(this.size() - 1);
        if (this._leaf === null || this._compare(value, this._leaf) > 0) {
            this._leaf = value;
        }
        return this;
    }

    /**
     * Inserts a new value into the heap
     * @public
     * @param {number|string|object} value
     * @returns {Heap}
     */
    push(value) {
        return this.insert(value);
    }

    /**
     * Removes and returns the root node in the heap
     * @public
     * @returns {number|string|object}
     */
    extractRoot() {
        if (this.isEmpty()) {
            return null;
        }

        const root = this.root();
        this._nodes[0] = this._nodes[this.size() - 1];
        this._nodes.pop();
        this._heapifyDown(0);

        if (root === this._leaf) {
            this._leaf = this.root();
        }

        return root;
    }

    /**
     * Removes and returns the root node in the heap
     * @public
     * @returns {number|string|object}
     */
    pop() {
        return this.extractRoot();
    }

    /**
     * Applies heap sort and return the values sorted by priority
     * @public
     * @returns {array}
     */
    sort() {
        for (let i = this.size() - 1; i > 0; i -= 1) {
            this._swap(0, i);
            this._heapifyDownUntil(i);
        }
        return this._nodes;
    }

    /**
     * Fixes node positions in the heap
     * @public
     * @returns {Heap}
     */
    fix() {
        for (let i = 0; i < this.size(); i += 1) {
            this._heapifyUp(i);
        }
        return this;
    }

    /**
     * Verifies that all heap nodes are in the right position
     * @public
     * @returns {boolean}
     */
    isValid() {
        const isValidRecursive = (parentIndex) => {
            let isValidLeft = true;
            let isValidRight = true;

            if (this._hasLeftChild(parentIndex)) {
                const leftChildIndex = (parentIndex * 2) + 1;
                if (this._compareAt(parentIndex, leftChildIndex) > 0) {
                    return false;
                }
                isValidLeft = isValidRecursive(leftChildIndex);
            }

            if (this._hasRightChild(parentIndex)) {
                const rightChildIndex = (parentIndex * 2) + 2;
                if (this._compareAt(parentIndex, rightChildIndex) > 0) {
                    return false;
                }
                isValidRight = isValidRecursive(rightChildIndex);
            }

            return isValidLeft && isValidRight;
        };

        return isValidRecursive(0);
    }

    /**
     * Returns a shallow copy of the heap
     * @public
     * @returns {Heap}
     */
    clone() {
        return new Heap(this._compare, this._nodes.slice(), this._leaf);
    }

    /**
     * Returns the root node in the heap
     * @public
     * @returns {number|string|object}
     */
    root() {
        if (this.isEmpty()) {
            return null;
        }

        return this._nodes[0];
    }

    /**
     * Returns the root node in the heap
     * @public
     * @returns {number|string|object}
     */
    top() {
        return this.root();
    }

    /**
     * Returns a leaf node in the heap
     * @public
     * @returns {number|string|object}
     */
    leaf() {
        return this._leaf;
    }

    /**
     * Returns the number of nodes in the heap
     * @public
     * @returns {number}
     */
    size() {
        return this._nodes.length;
    }

    /**
     * Checks if the heap is empty
     * @public
     * @returns {boolean}
     */
    isEmpty() {
        return this.size() === 0;
    }

    /**
     * Clears the heap
     * @public
     */
    clear() {
        this._nodes = [];
        this._leaf = null;
    }

    /**
     * Builds a heap from a array of values
     * @public
     * @static
     * @param {array} values
     * @param {function} compare
     * @returns {Heap}
     */
    static heapify(values, compare) {
        if (!Array.isArray(values)) {
            throw new Error('Heap.heapify expects an array of values');
        }

        if (typeof compare !== 'function') {
            throw new Error('Heap.heapify expects a compare function');
        }

        return new Heap(compare, values).fix();
    }

    /**
     * Checks if a list of values is a valid heap
     * @public
     * @static
     * @param {array} values
     * @param {function} compare
     * @returns {boolean}
     */
    static isHeapified(values, compare) {
        return new Heap(compare, values).isValid();
    }
}

/**
 * @class PriorityQueue
 */
class PriorityQueue {
    /**
     * 创建优先队列
     * @params {function} compare 优先级判定规则
     * @params {_values} 初始数组，会自动调整队列顺序
     */
    constructor(compare, _values) {
        if (typeof compare !== 'function') {
            throw new Error('PriorityQueue constructor expects a compare function');
        }
        this._heap = new Heap(compare, _values);
        if (_values) {
            this._heap.fix();
        }
    }

    /**
     * 返回队头元素（优先级最高）
     * @public
     * @returns {number|string|object}
     */
    front() {
        return this._heap.root();
    }

    /**
     * 返回队尾元素（优先级最低）
     * @public
     * @returns {number|string|object}
     */
    back() {
        return this._heap.leaf();
    }


    /**
     * 入队
     * @public
     * @param {number|string|object} value
     * @returns {PriorityQueue}
     */
    push(value) {
        return this._heap.insert(value);
    }

    /**
     * 队首出队
     * @public
     * @returns {number|string|object}
     */
    pop() {
        return this._heap.extractRoot();
    }

    /**
     * 返回队列元素个数
     * @public
     * @returns {number}
     */
    size() {
        return this._heap.size();
    }

    /**
     * 判空
     * @public
     * @returns {boolean}
     */
    isEmpty() {
        return this._heap.isEmpty();
    }

    /**
     * 清除队列
     * @public
     */
    clear() {
        this._heap.clear();
    }
}
